Definitions:
S:“the set S”|S|:“the number of elements in S.”|x|:“the number of characters in ‘x’”S U s:“the addition of element s to S”<v1, . . . vn>:“the n-tuple of values vi”→:“maps to”
The subject invention relates to deterministic matching of objects or events in a first set with objects or events in a second set when the objects or events are not all uniquely identified. More particularly it relates to matching letters to events which occur during the delivery of such letters. By “deterministic matching” herein is meant matching of events (or elements in the second set) to letters (or elements in the first set) if and only if sufficient information is available to uniquely associate events with particular letters.
It is often useful to be able to match objects or events in a first set with objects or events in other sets. For example, a hypothetical automobile assembly process may require that a particular engine be assembled with a particular style body, paint color, etc. to produce a car as ordered. An effective way to achieve this is to associate codes with the objects or events to be matched so that objects or events which match are associated with the same code. This a relatively simple process where the codes suffice to uniquely identify the objects or events within each set. However, if the codes are not sufficient to uniquely identify the objects or events which match, the task of matching becomes much more difficult. Thus, in the automotive example given above, if order number 123456 calls for a high performance engine but the engine is coded 12345; either because of a mistake or because of a systematic problem (e.g. the engine encoder can only specify 5 digits) it may or may not be possible to deterministically match the engine to an order. Assuming that it is desirable that orders be filled in the normal process where possible, but more important that no unordered cars be assembled; the need for a deterministic matching method can be seen.
An actual example of a process in which a deterministic matching method can be used to good effect is the mail tracking program recently introduced by the United States Postal Service (hereinafter sometimes “USPS”)under the trademark CONFIRM®. The CONFIRM program tracks mailpieces through the delivery process and provides the mailer with information about the status of the mailpiece in the delivery process.
FIG. 1 shows a simplified representation of the USPS mailpiece delivery process incorporating the CONFIRM mail tracking process. Mailers 10 deliver large mailings 12 to local postal facilities 14. Mailings 12 can comprise letters, flats, periodicals, or the like (sometimes hereinafter generally “letters”) and are typically pre-sorted to various degrees by mailers 10 to obtain discounts offered by the USPS. (While the general principles of the CONFIRM process can be applied to any mailpiece or package, as currently implemented by the USPS it used for tracking large, typically pre-sorted, mailings and reply mail returned in pre-addressed and pre-coded business reply envelopes (sometimes herein “BRE's”) sent out in such mailings.)
At facility 14 scanner 16 scans mailings 12 to establish the times at which mailings 12 entered the mail delivery process. Typically individual letters are not scanned at facility 14, though they can be if appropriate scanners are available, and accompanying documents(not shown) are scanned to establish the time and facility at which each of mailings 12 entered the delivery process and/or the times at which mailings 12 are sent on in the delivery process. This information is then sent to programmable data processing system (hereinafter sometimes server) 22 over one of communications links 20. (Links 20 connect various postal facilities to server 22 and can take any convenient form or forms; details of which form no part of the subject invention.) Mailings 12 and other mailpieces (not shown) are then grouped to form assemblies 28 which are then delivered to sectional postal center 30. At center 30 assemblies 28, together with other assemblies 28 from other facilities (not shown) are processed by conventional high speed scanner/sorters 32. As letters are sorted and otherwise processed at center 30 a POSTNET code (commonly known as a “zipcode” and hereinafter sometimes “pn”) and a code used in the CONFIRM process known by the USPS trademark PLANET Code® (hereinafter sometimes “pc”) are scanned from the letters. The pair <pn, pc> identify, though not necessarily uniquely identify, the letters within a set of letters, and events associated with those letters, as will be described further below. In accordance with USPS requirements the POSTNET Code and PLANET Code are printed as barcodes. As letters are scanned, typically for the first time at center 30, the values pn and pc are sent to sever 22 over one of links 20, where they are combined with information about mailings 12 from facility 14, as will be described further below. (Note that the PLANET Code for a letter will identify a corresponding mailing so that the time a letter entered the mail delivery process can be determined by sever 22 from information provided by facility 14.)
Sorted assemblies 36 are delivered to local postal facilities 38 for further sorting and delivery of letters l. Letters l can be scanned at facilities by scanners 40 and information including values for pn and pc sent to server 22 over one of links 20. BRE's included in mailings 12 can be returned by the receiving customers and are scanned, sorted and delivered in substantially the same manner as described above, except that BRE's are typically returned as individual letters and, of course need not follow the same path through the postal system as mailings 12.
As a letter moves through the delivery process and various steps or stages occur (hereinafter sometimes “events”) and these events are recorded as an n-tuple <d, f, t, pn, pc> where:    d is the time at which the event occurred;    f is the facility at which the event occurred;    t is the type of event;    pn is the POSTNET (possibly partial) scanned from the letter when the event occurs; and    pc is the PLANET Code scanned from the letter when the event occurs.Server 22 is programmed to match these events with letters having corresponding values for the pair <pn, pc> and maintain database 24 of matched letters and events. Mailers 10 can then access database 24 through server 22 and network 42, or in any other convenient manner, to determine the status of letters in the mail delivery system. However the <pn, pc> data is often incomplete or inaccurate. Further, different letters may have the same values for <pn, pc>. Thus it is not always possible to uniquely match an event and a corresponding letter. Since mailers would rather have no tracking information than incorrect information, there is a need for a deterministic method and system which will match letters and events in the context of the USPS CONFIRM system. Current methods for matching letters and events attempt to match only those cases where the full (11 digit) POSTNET code and PLANET Code are scanned and allow matching of approximately 80 to 85% of events to letters; rejecting the remaining 15 to 20%.
Program code to control server 22 in accordance with the subject invention is provided on magnetic or optical disk 46-D and input through disk reader 46-R, or through any other suitable computer readable medium. The term “computer-readable medium” as used herein refers to any medium that participates in providing program code to a processor for execution. Such a medium may take many forms, including but not limited to, non-volatile media, volatile media, and transmission media. Non-volatile media includes, for example, optical or magnetic disks, or random access read only memory. Volatile media includes random access dynamic memory. Transmission media includes coaxial cables, copper wire and fiber optics. Transmission media can also take the form of acoustic or light waves, such as those generated during radio wave and infrared data communications. By “program code” herein is meant sequences of indicia recorded on, or signals transmitted by, computer readable media, which, when input by a processor cause a processor to carry out a corresponding sequence of operations, i.e. execute the program code.
In FIG. 2 letter l includes a delivery address printed in block 50, a return address printed in block 52, a stamp or postal indicium indicating payment of postage 54, PLANET Code barcode 56, and POSTNET barcode 58. Letter l can be printed with additional markings which do not relate to the subject invention and can be arranged in somewhat different formats without affect on the teaching of the present application. Barcode 58 typically represents 5, 9, or 11 digits which specify delivery information with increasing precision. The code used is typically determined by the information available to mailer 10 or by the extent which mailer 10 wishes to pre-sort mailings 12. PLANET Code 56 can take on one of two formats, format 56-D to track delivery of letters in mailings 12 and format 56-0 to track BRE's returned by customers. Format 56-D specifies the service (e.g. first class letters, standard mail flats, etc.) subscriber (i.e. mailer) id, and mailing id. Typically there is one PLANET Code used in a mailing. Format 56-0 specifies the service and a customer id. The CONFIRM system relies on the BRE's POSTNET code to identify the mailer.
While generally the POSTNET and PLANET Code, i.e. the pair<pn, pc>, uniquely specify a letter it is apparent that this need not be so. For example, if a mailer 10 chooses not to sort a mailing 12, letters in that mailing may only have a 5 digit POSTNET code with many letters having the same value for pn. Or scanners at various facilities may not have a capability to scan a full 11 digit POSTNET code so that a event record can not always be uniquely associated with a letter record. More rarely, even the full POSTNET code will not distinguish all letters, as when two letters in a mailing are sent to the same address. (Since the CONFIRM system is relatively new it is believed all PLANET Code scanners can scan the full PLANET Code.)
(The above simplified description of the mail delivery process and the CONFIRM system is given to provide background and those skilled in the art will recognize that substantial differences from actual mail delivery can exist. Such differences however are not believed to affect the present teaching. Further details of the CONFIRM system are found in: The CONFIRM® System Customer Service Guide, United States Postal Service, publication no. 197, September 2002.)
Thus it is an object of the subject invention to provide a method and system for deterministic matching of objects and events, such as letters and events occurring as the letters are delivered, even though the letters and events are not necessarily uniquely identified.